package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/6 12:52
 * @DESCRIPTION
 */
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集
// 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
// 输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
public class 子集2 {
    LinkedList<Integer> path=new LinkedList<>();//路径
    List<List<Integer>> res=new ArrayList<>();//最终结果
    public List<List<Integer>> method1(int[] nums) {
        //数组中有重复元素的常规操作
        //数组排序+循环判断 continue
        Arrays.sort(nums);
        recursion(0,nums);
        return res;
    }
    public void recursion(int head,int[]nums){
        res.add(new ArrayList<>(path));
        if (head>=nums.length){
            return;
        }
        for(int i=head;i<nums.length;i++){
            //循环判断 continue
            if(i>head&&nums[i]==nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            recursion(i+1,nums);
            path.removeLast();
        }
    }

    public List<List<Integer>> practice(int[] nums) {
        res.add(new ArrayList<>());
        if(nums.length==0){
            return res;
        }
        Arrays.sort(nums);
        recursionPractice(nums,0);
        return res;
    }

    private void recursionPractice(int[] nums, int startIndex) {
        for (int i = startIndex; i < nums.length; i++) {
            //对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。
            //这是针对于宽度上的重复选择
            //而深度上的不需要避免重复选择 因为[1,2,2]  1,2 \1,2,2\2,2 都是可以的 ，可见深度上是把每个重复的数一起加进来
            //而不是像宽度上那样，选了一个的数，然后在下一次回溯，不要这个数，选择下一个数，如果这两次的数是相同时，必然会产生重复
            if(i>startIndex&&nums[i]==nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            res.add(new ArrayList<>(path));
            recursionPractice(nums,i+1);
            path.removeLast();
        }
    }
}
